1. Field of the Invention
The present invention relates to a control scheduler for an ATM network and, more specifically, to a scheduler which guarantees minimum rate of transmission, while fairly distributes any unused bandwidth.
2. Description of Related Art
High-speed networks based on the Asynchronous Transfer Mode (ATM) are expected to carry services with a wide range of traffic characteristics and quality-of-service (QoS) requirements. For example, in audio transmission a cell is useless to the receiver if it is delayed beyond the specified rate. On the other hand, video transmission is very bursty and, unless shaped at the entry point, may cause temporary congestion and delay other cells. Integrating all services in one network with a uniform transport mechanism can potentially simplify network operation and improve network efficiency. In order to realize these potential benefits, an efficient and fair means of allocating the network resources is essential.
A central problem in allocating the network resources is the manner in which the service to the various users is prioritized. A simple model is to use a First In First Out (FIFO) algorithm. In a simple First-In First-Out (FIFO) scheduler, there is no way of guaranteeing that each stream gets its assigned rate. During some interval of time, a given stream may transmit at a rate higher than its assigned rate Mi, and thereby steal bandwidth from other streams which are transmitting at or below their assigned rates. This problem led to the development of various mechanisms for shaping the entry to the network, such as the known leaky bucket algorithm. For example, the output stream for each queue can be peak rate shaped to a predetermined rate Mp.
FIG. 1 shows a static rate control (SRC) scheduler with N-stream queues, SQ1, SQ2 . . . SQN, one queue corresponding to each stream. The SRC scheduler serves a queue i at the constant rate Mi and the output cell streams are fed to a common bottleneck queue CQ which is served at a given rate C. Service from the common queue CQ corresponds to cell transmission over a link of capacity C.
Rate-shaping transforms the streams into constant rate streams (assuming all queues are continuously backlogged). Considering the relationship                                           ∑                          i              =              1                        N                    ⁢                      M            i                          ≤                  C          .                                    (        1        )            
(to be developed further below), the bottleneck queue will be stable; in fact, the maximum queue length is N. In fact, strict inequality in (1) will usually hold, implying that the cell delay in the common queue will be small with high probability. Although the service discipline depicted in FIG. 1 is work-conserving with respect to the stream queues, it is non-work-conserving with respect to the common queue, since it is possible that the common queue may go empty even when at least one of the stream queues is non-empty. This scheduler is similar to a circuit-switched system, except for the asynchronous nature of the cell streams.
If the rates, Mi, have been computed correctly based on the stream traffic characteristics and QoS requirements, the minimum rate scheduler should succeed in guaranteeing QoS for all of the streams. However, because this scheduler is non-work-conserving with respect to the common queue, bandwidth could be wasted for one of two reasons:
The CAC algorithm was optimistic in its computation of Mi. It may be the case that a bandwidth of Mi+xcex94 over short intervals of time is required to ensure that QoS is met for stream i.
The traffic stream could include low priority cells, with the cell loss priority (CLP) bit set to one.
In the first case, a stream should be allowed to make use of bandwidth beyond its allocated rate, Mi, if the bandwidth is available. In the second case, the QoS guarantee applies only to cells that conform to the negotiated traffic contract, i.e., cells with cell loss priority (CLP) set to zero. However, if bandwidth is available, a stream should be permitted to transmit nonconforming cells, i.e., cells tagged as CLP=1 cells, over and above the allocated minimum rate for CLP=0 cells. If bandwidth is not available, CLP=1 cells should be dropped before CLP=0 cells; i.e., there should be a lower threshold for dropping CLP=l cells. (As is known in the art, when a source transmits at a rate higher than the negotiated rate, its violating cells are tagged by setting their CLP to 1.)
Clearly, the problem with the minimum rate scheduler, is that streams cannot make use of excess bandwidth even when it is available. In minimum rate scheduling, there is no statistical multiplexing among cells belonging to different streams. (As is known in the art, statistical multiplexing takes into account xe2x80x9ceconomies of scale,xe2x80x9d i.e., the bandwidth it takes to transmit all the streams together is less than the sum of the individual bandwidths required to transmit each stream.) A simple way to enhance this scheme is to provide means for serving a cell from a non-empty queue whenever bandwidth is available. During a cell time, if the common queue is empty, the scheduler services a cell from one of the non-empty stream queues.
According to another prior art method, the queue selection is done in a round-robin fashion, and the excess bandwidth i s shared equally among the active streams. A disadvantage of such a scheduler is that queues are served without regard to QoS. That is, the bandwidth is alternated sequentially to the queues without regard to the urgency of transmission, i.e., requested minimum rate, of any specific source. Therefore, this method does not lend itself well for serving different classes having different QoS requirements.
Accordingly, there has been considerable interest in packet scheduling algorithms which are intended to provide weighted shares of the bandwidth on a common link to competing traffic streams, so as to enable service of different classes. With slightly more complexity, the excess bandwidth can be shared using Weighted Round-Robin (WRR) Weighted Fair Queuing (WFQ), and Virtual Clock, and their variants, which attempt to approximate the idealized Generalized Processor Sharing (GPS) scheduling, assuming a fluid model of traffic. For WRR, see M. Katevenis, S. Sidiropoulos, and C. Courcoubetis, Weighted Round-Robin Cell Multiplexing in a General-Purpose ATM Switch, IEEE JSAC, Vol 9, pp. 1265-1279, October 1991. For WFQ, see, A. K. Parekh and R. G. Gallager, A generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: The Single-Node Case, IEEE/ACM Trans. on Networking, vol. 1, pp. 344-357, June 1993. For Virtual Clock, see, L. Zhang, Virtual Clock: A New Traffic Control Algorithm for Packet Switching, ACM Trans. on Computer Systems, vol. 9, pp. 101-124, May 1991. In these schedulers, each stream is assigned a weight corresponding to the QoS requested by a user of the stream. Accordingly, over an interval of time in which the number of active streams is fixed, the bandwidth received by an active stream should be roughly proportional to the assigned weight.
By an appropriate assignment of weights, each stream can be provided with a share of the link bandwidth that is proportional to its weight. Hence, each stream receives a minimum bandwidth guarantee. If a stream cannot make use of all of its guaranteed bandwidth, the excess bandwidth is shared among the active streams in proportion to the weights. However, a stream with a larger weight will not only receive a higher bandwidth guarantee, but also receive larger shares of the available bandwidth than streams with smaller weights. Thus, the weight assigned to a connection determines not only its minimum bandwidth guarantee, but also its share of the available unused bandwidth.
In this specification the term xe2x80x9cweighted fair share schedulerxe2x80x9d is used generally to refer to a general class of work-conserving schedulers which schedule cells so as to give each stream a share of the link bandwidth which is approximately proportional to a pre-assigned weight. A work-conserving scheduler transmits a cell over the link whenever there is at least one cell in queue. Thus, a work-conserving scheduler basically determines the order in which queued cells should be serviced. The operation of such a scheduler is described in the following.
Consider an idealized fluid model for each traffic stream. Let wi be the weight assigned to stream i. At time t, the Generalized Processor Sharing (GPS) discipline serves stream i at rate:                                                         R              i                        ⁡                          (              t              )                                =                                                    w                i                                                              ∑                                      j                    ∈                                          A                      ⁡                                              (                        t                        )                                                                                            ⁢                                  w                  j                                                      ⁢            C                          ,                  i          ∈                      A            ⁡                          (              t              )                                      ,                            (        2        )            
where A(t) is the set of backlogged streams at time t. Thus, each stream always receives a share of the available bandwidth which is proportional to its weight. Because of the discrete nature of cells or packets, a real scheduler can only approximate GPS scheduling. PGPS (Packet-by packet Generalized Processor Sharing), also known as Weighted Fair Queuing (WFQ) noted above, and its variants (cf. S. J. Golestani, A Self-Clocked Fair Queuing Scheme for Broadband Applications, in IEEE INFOCOM ""94, Toronto, June 1994; and J. C. R. Bennett and H. Zhang, WF2Q: Worst-Case Fair Weighted Fair Queuing, in IEEE INFOCOM ""96, San Francisco, pp. 120-128, March 1996) are schedulers which approximate GPS for packet scheduling. Other examples of scheduling schemes which attempt to achieve fair sharing are the Virtual Clock and Weighted Round-Robin noted above. Several other weighted fair share schedulers have been proposed in the literature.
It should be appreciated that the assigned weight and the current usage of the network would determine whether a QoS requested by an incoming call can be guaranteed. Therefore, various Connection Admission Control (CAC) algorithms have been developed which decline service when the QoS cannot be guaranteed. For that matter, the CAC algorithm must be able to predict the load on the system, including the newly received call if admitted. Therefore, delay bounds have been found for WRR, WFQ, Virtual Clock and other fair share packet scheduling algorithms. Using these delay bounds, admission control schemes can be devised to provide worst-case delay guarantees. The delay bounds are typically obtained by assuming worst-case behavior for streams controlled by leaky bucket-type open-loop flow control mechanisms. However, a problem in such an algorithm is that the calculated bounds tend to be rather loose, since worst-case deterministic assumptions are made in obtaining the bounds.
Another problem with the prior art schedulers is as follows. Conventionally, schedulers have been designed so that they are work-conserving with respect to the stream queues, in the sense that whenever link bandwidth is available and a packet is in the queue, a packet will be transmitted over the link. In other words, if a packet is available for transmission and there is sufficient bandwidth, the packet will be transmitted and the scheduler will not idle. The work-conserving approach has been promoted in the prior art since it presumably results in the highest possible utilization over the link.
However, within a switching system or the network, there may be several bottlenecks. For example, some of the streams may be bottlenecked at a downstream link at another stage within the switch or the network. In this case, providing these streams more bandwidth than their minimum guaranteed rates (when bandwidth is available) could exacerbate the congestion at the downstream bottleneck. Such congestion cannot be alleviated by the prior art schedulers because they are work-conserving with respect to a single bottleneck, servicing cells only in accordance with the available bandwidth at this bottleneck. That is, conventional weighted fair share schedulers always ensure that excess bandwidth is utilized and that the share of excess bandwidth made available to each queue is proportional to its weight, but they do no exercise control on the absolute value of the rate received at a bottleneck point.
Additionally, if there is a downstream bottleneck, typically backpressure signals which throttle upstream traffic are used to alleviate congestion. However, backpressure signals are susceptible to on/off oscillations, resulting in higher cell delay variation (CDV) and, more significantly, loss of throughput due to the equalization of bandwidth distribution. That is, in the prior art when a buffer reaches its limit, a backpressure signal is sent to the source. Upon receiving the signal the source would stop transmission until the buffer signals that the pressure was relieved. However, at that time it is likely that all the sources would start transmission again concurrently, thereby overloading the buffer again so that the backpressure signal is again generated. Therefore, the system may oscillate for sometime causing large variation in cell delay. Additionally, since all the sources would stop and start transmission at the same time, the throughput would be equalized irrespective of the QoS requested by each source.
Since weighted fair share schedulers schedule cells only with respect to a single bottleneck, throughput for a cell stream may suffer because of backpressure resulting from downstream congestion. Hence, it may not be possible to guarantee a minimum throughput in this case. Consequently, while the prior art weighted share scheduler is work-conserving with respect to a bottleneck link, it may be non-work-conserving with respect to a downstream bottleneck. Thus, the present inventors have determined that work-conservation is not always a desirable property and may lead to further congestion downstream.
Yet another problem with the prior art weighted fair scheduling is that they necessitate an algorithm for searching and sorting out the timestamps applied to the cells in order to determine the next queue to service. More specifically, in the prior art the time stamps are relative, i.e., the scheduler needs to continuously order the cells according to their timestamp. For example, the scheduler may order the cells according to the length of the timestamp or according to the time remaining before the cell would be discarded. Such calculations may slow down the scheduler.
As is known in the art, the ATM Forum has established four main classes of traffic, generally divided into real time traffic and non-real time traffic. Constant Bit Rate (CBR) and Variable Bit Rate (VBR) are used for real time traffic, e.g., audio and video. Available Bit Rate (ABR) and Unspecified Bit Rate (UBR) are non-real time traffic, and are mainly used for computer communication. As can be appreciated, ABR traffic has no minimum rate requirement and the main goal in scheduling ABR cells is to xe2x80x9cpumpxe2x80x9d as many cells as possible using the available bit rate.
a dual proportional-derivative (PD) controller for ABR service has been proposed in A Kolarov and G. Ramamurthy, Design of a Closed Loop Feed Back Control for ABR Service, in Proc. IEEE INFOCOM ""97, Kobe Japan, April 1997. The scheduler is implemented on a network-wide basis using resource management (RM) cells. Generally, the source generates RMCEs which propagate through the network. As each RMC cell passes through a switch, it is updated to indicate the supportable rate, i.e., the rate the source should transmit the data (generally called explicit rate). These RMC cells are fed back to the source so that the source may adjust its transmission rate accordingly. However, the propagation of the RMCs through the network causes a large delay in controlling the source. While such delay is acceptable for scheduling ABR cells, it is unacceptable for scheduling real time trafic. Moreover, the delay need to be accounted for by the scheduler, which complicates the computations and slows down the scheduler.
The present invention provides a new scheduling scheme which uses statistical approaches to admission control so as to provide much higher utilizations, while maintaining the guaranteed QoS. The general concept of the present invention is do construct the rate from two components: (1) a minimum guaranteed rate, and (2) a portion of the unused bandwidth. Constructing the rate from two components allows the scheduler to operate under at least three modes: (1) full available rate (i.e., minimum guaranteed rate plus a portion of the unused bandwidth), (2) minimum guaranteed rate, and (3) halt transmission (with very small probability). In its preferred form, inventive scheduling scheme decouples the minimum guaranteed rate from the portion of unused bandwidth and is called Dynamic Rate Control (DC).
The DRC first distributes the bandwidth so as to support the guaranteed QoS, i.e., it supports the minimum guaranteed rate. Then, the DRC distributes any unused bandwidth to users, based upon a criteria which, in the preferred embodiment, is independent of the minimum rate guaranteed to the users. A notable feature of the inventive DRC is that it is not necessarily work conserving, but rather takes into account bottlenecks downstream in determining whether to allocate unused bandwidth.
As noted above, a disadvantage of the prior art weighted fair sharing is that the entire bandwidth is allocated according to the assigned weight. However, it might be desirable to determine the service rate according to:                                                         R              i                        ⁡                          (              t              )                                =                                    M              i                        +                                                            w                  i                  xe2x80x2                                                                      ∑                                          j                      ∈                                              A                        ⁡                                                  (                          t                          )                                                                                                      ⁢                                      w                    j                    xe2x80x2                                                              ⁢                              E                ⁡                                  (                  t                  )                                                                    ,                            (        10        )            
where, in general, wljxe2x89xa0wj. In Eq. (10), the minimum rate guarantee and the excess bandwidth for a stream are decoupled. This decoupling allows the network provider to distribute the unused bandwidth independently of the minimum guaranteed rates. The inventive DRC scheduler naturally decouples the minimum rate guarantee from the excess bandwidth allocated to a stream. weights can be assigned on a per-class basis by the CAC or dynamically via a closed-loop QoS control mechanism.
Thus, for example, for UBR it may be preferable to assign very small or even zero guaranteed minimum rate, but to provide a large portion of the available bandwidth. This will help satisfy many real-time calls, while providing service for non-real time UBR when there is bandwidth available.
Also noted above is that since work-conserving schedulers transmit a cell whenever there is at least one cell in a queue, it only determines the order in which queued cells should be serviced. By contrast, a non-work-conserving scheduler may allow a cell time on the link to go idle even if there are cells in queue. Hence, in addition to the ordering of cells for service, timing is also important in non-work-conserving schedulers. Therefore, the present inventors have developed mechanisms to account for both ordering and timing of cell transmission. However, unlike the prior art, in the present invention the timestamp are absolute, rather than relative. That is, at any given current time, CT, any cell having a timestamp which equals the current time is eligible for service. Therefore, there is no need for constant ordering of the cells according to timestamps.